package offer;

import java.util.Arrays;

public class Offer51 {



    private  void mergeAndCount(int[] arr, int l, int m, int r)
    {
        int[] left = Arrays.copyOfRange(arr, l, m + 1);

        int[] right = Arrays.copyOfRange(arr, m + 1, r + 1);

        int i = 0, j = 0, k = l;

        while (i < left.length && j < right.length) {
            if (left[i] <= right[j])
                arr[k++] = left[i++];
            else {
                arr[k++] = right[j++];
                count += (m + 1) - (l + i);
            }
        }

        while (i < left.length)
            arr[k++] = left[i++];

        while (j < right.length)
            arr[k++] = right[j++];


    }

    int count = 0;
    // 归并排序
    private void mergeSortAndCount(int[] arr, int l, int r)
    {

        if (l < r) {
            int m = (l + r) / 2;

             mergeSortAndCount(arr, l, m);

             mergeSortAndCount(arr, m + 1, r);

             mergeAndCount(arr, l, m, r);
        }

//        return count;
    }


    public int reversePairs(int[] nums) {
         mergeSortAndCount(nums, 0, nums.length-1);
         return count;
    }





    public static void main(String[] args) {
        int[]  arr={1,3,2,3,1};
        Offer51 offer51 = new Offer51();
        int i = offer51.reversePairs(arr);
        System.out.println(i);
        for (int a: arr
             ) {
            System.out.println(a);

        }
    }



    }

